package Leetcode.DayTest;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: kirito
 * @Date: 2025/4/9 10:32
 * @Description:
 */

public class 使数组和能被P整除 {
    public static void main(String[] args) {
        int[] arr = {1000000000,1000000000,1000000000};
        int p = 3;
        System.out.println(minSubarray(arr, p));
    }
    public static int minSubarray(int[] nums, int p) {
        int n = nums.length;
        int[] s = new int[n + 1];
        //前缀和
        for (int i = 0; i < n; i++) {
            s[i + 1] = (s[i] + nums[i]) % p;
        }

        int x = s[n];
        if (x == 0) return 0; // 如果总和已经是p的倍数，则不需要移除任何子数组

        Map<Integer, Integer> last = new HashMap<>();
        int ans = n; // 初始化为最大子数组长度
        for (int i = 0; i <= n; i++) {
            last.put(s[i], i);
            // 计算需要查找的键值
            int key = (s[i] - x + p) % p;
            // 如果map中存在该键，则计算子数组长度
            if (last.containsKey(key)) {
                ans = Math.min(ans, i - last.get(key));
            }
        }

        // 如果没有找到有效的子数组，返回-1
        return ans < n ? ans : -1;
    }

}
